﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_108_SortedArrayToBST
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { -10, 3, 0, 5, 9 };
            Console.WriteLine(SortedArrayToBST(nums));
            Console.ReadKey();
        }
        public static TreeNode SortedArrayToBST(int[] nums)
        {
            return SetTreeNodeValue(nums, 0, nums.Length - 1);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static TreeNode SetTreeNodeValue(int[] nums,int a, int b)
        {
            if (a>b)
            {
                return null;
            }

            int index = (a + b) / 2;
            TreeNode root = new TreeNode(nums[index]);

            root.left = SetTreeNodeValue(nums, a, index-1);
            root.right = SetTreeNodeValue(nums, index+1,b);
            return root;
        }
    }
}
